home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / Graphic Gems I, II & III (C_C++) / Graphics Gems C Code.sea / GemsI / Src / ConcaveScan.c < prev    next >
Text File  |  1992-06-16  |  5KB  |  151 lines
  1. /*
  2.  * Concave Polygon Scan Conversion
  3.  * by Paul Heckbert
  4.  * from "Graphics Gems", Academic Press, 1990
  5.  */
  6.  
  7. /*
  8.  * concave: scan convert nvert-sided concave non-simple polygon with vertices at
  9.  * (point[i].x, point[i].y) for i in [0..nvert-1] within the window win by
  10.  * calling spanproc for each visible span of pixels.
  11.  * Polygon can be clockwise or counterclockwise.
  12.  * Algorithm does uniform point sampling at pixel centers.
  13.  * Inside-outside test done by Jordan's rule: a point is considered inside if
  14.  * an emanating ray intersects the polygon an odd number of times.
  15.  * drawproc should fill in pixels from xl to xr inclusive on scanline y,
  16.  * e.g:
  17.  *    drawproc(y, xl, xr)
  18.  *    int y, xl, xr;
  19.  *    {
  20.  *        int x;
  21.  *        for (x=xl; x<=xr; x++)
  22.  *        pixel_write(x, y, pixelvalue);
  23.  *    }
  24.  *
  25.  *  Paul Heckbert    30 June 81, 18 Dec 89
  26.  */
  27.  
  28. #include <stdio.h>
  29. #include <math.h>
  30. #include "GraphicsGems.h"
  31.  
  32. #define ALLOC(ptr, type, n)  ASSERT(ptr = (type *)malloc((n)*sizeof(type)))
  33.  
  34. typedef struct {        /* window: a discrete 2-D rectangle */
  35.     int x0, y0;            /* xmin and ymin */
  36.     int x1, y1;            /* xmax and ymax (inclusive) */
  37. } Window;
  38.  
  39. typedef struct {        /* a polygon edge */
  40.     double x;    /* x coordinate of edge's intersection with current scanline */
  41.     double dx;    /* change in x with respect to y */
  42.     int i;    /* edge number: edge i goes from pt[i] to pt[i+1] */
  43. } Edge;
  44.  
  45. static int n;            /* number of vertices */
  46. static Point2 *pt;        /* vertices */
  47.  
  48. static int nact;        /* number of active edges */
  49. static Edge *active;        /* active edge list:edges crossing scanline y */
  50.  
  51. int compare_ind(), compare_active();
  52.  
  53. concave(nvert, point, win, spanproc)
  54. int nvert;            /* number of vertices */
  55. Point2 *point;            /* vertices of polygon */
  56. Window *win;            /* screen clipping window */
  57. void (*spanproc)();        /* called for each span of pixels */
  58. {
  59.     int k, y0, y1, y, i, j, xl, xr;
  60.     int *ind;        /* list of vertex indices, sorted by pt[ind[j]].y */
  61.  
  62.     n = nvert;
  63.     pt = point;
  64.     if (n<=0) return;
  65.     ALLOC(ind, int, n);
  66.     ALLOC(active, Edge, n);
  67.  
  68.     /* create y-sorted array of indices ind[k] into vertex list */
  69.     for (k=0; k<n; k++)
  70.     ind[k] = k;
  71.     qsort(ind, n, sizeof ind[0], compare_ind);    /* sort ind by pt[ind[k]].y */
  72.  
  73.     nact = 0;                /* start with empty active list */
  74.     k = 0;                /* ind[k] is next vertex to process */
  75.     y0 = MAX(win->y0, ceil(pt[ind[0]].y-.5));        /* ymin of polygon */
  76.     y1 = MIN(win->y1, floor(pt[ind[n-1]].y-.5));    /* ymax of polygon */
  77.  
  78.     for (y=y0; y<=y1; y++) {        /* step through scanlines */
  79.     /* scanline y is at y+.5 in continuous coordinates */
  80.  
  81.     /* check vertices between previous scanline and current one, if any */
  82.     for (; k<n && pt[ind[k]].y<=y+.5; k++) {
  83.         /* to simplify, if pt.y=y+.5, pretend it's above */
  84.         /* invariant: y-.5 < pt[i].y <= y+.5 */
  85.         i = ind[k];    
  86.         /*
  87.          * insert or delete edges before and after vertex i (i-1 to i,
  88.          * and i to i+1) from active list if they cross scanline y
  89.          */
  90.         j = i>0 ? i-1 : n-1;    /* vertex previous to i */
  91.         if (pt[j].y <= y-.5)    /* old edge, remove from active list */
  92.         delete(j);
  93.         else if (pt[j].y > y+.5)    /* new edge, add to active list */
  94.         insert(j, y);
  95.         j = i<n-1 ? i+1 : 0;    /* vertex next after i */
  96.         if (pt[j].y <= y-.5)    /* old edge, remove from active list */
  97.         delete(i);
  98.         else if (pt[j].y > y+.5)    /* new edge, add to active list */
  99.         insert(i, y);
  100.     }
  101.  
  102.     /* sort active edge list by active[j].x */
  103.     qsort(active, nact, sizeof active[0], compare_active);
  104.  
  105.     /* draw horizontal segments for scanline y */
  106.     for (j=0; j<nact; j+=2) {    /* draw horizontal segments */
  107.         /* span 'tween j & j+1 is inside, span tween j+1 & j+2 is outside */
  108.         xl = ceil(active[j].x-.5);        /* left end of span */
  109.         if (xl<win->x0) xl = win->x0;
  110.         xr = floor(active[j+1].x-.5);    /* right end of span */
  111.         if (xr>win->x1) xr = win->x1;
  112.         if (xl<=xr)
  113.         (*spanproc)(y, xl, xr);        /* draw pixels in span */
  114.         active[j].x += active[j].dx;    /* increment edge coords */
  115.         active[j+1].x += active[j+1].dx;
  116.     }
  117.     }
  118. }
  119.  
  120. static delete(i)        /* remove edge i from active list */
  121. int i;
  122. {
  123.     int j;
  124.  
  125.     for (j=0; j<nact && active[j].i!=i; j++);
  126.     if (j>=nact) return;    /* edge not in active list; happens at win->y0*/
  127.     nact--;
  128.     bcopy(&active[j+1], &active[j], (nact-j)*sizeof active[0]);
  129. }
  130.  
  131. static insert(i, y)        /* append edge i to end of active list */
  132. int i, y;
  133. {
  134.     int j;
  135.     double dx;
  136.     Point2 *p, *q;
  137.  
  138.     j = i<n-1 ? i+1 : 0;
  139.     if (pt[i].y < pt[j].y) {p = &pt[i]; q = &pt[j];}
  140.     else           {p = &pt[j]; q = &pt[i];}
  141.     /* initialize x position at intersection of edge with scanline y */
  142.     active[nact].dx = dx = (q->x-p->x)/(q->y-p->y);
  143.     active[nact].x = dx*(y+.5-p->y)+p->x;
  144.     active[nact].i = i;
  145.     nact++;
  146. }
  147.  
  148. /* comparison routines for qsort */
  149. compare_ind(u, v) int *u, *v; {return pt[*u].y <= pt[*v].y ? -1 : 1;}
  150. compare_active(u, v) Edge *u, *v; {return u->x <= v->x ? -1 : 1;}
  151.